{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Integer Divisible by K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestRepunitDivByK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可被 K 整除的最小整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定正整数 <code>k</code>&nbsp;，你需要找出可以被 <code>k</code>&nbsp;整除的、仅包含数字 <code><strong>1</strong></code> 的最 <strong>小</strong> 正整数 <code>n</code>&nbsp;的长度。</p>\n",
    "\n",
    "<p>返回 <code>n</code>&nbsp;的长度。如果不存在这样的 <code>n</code>&nbsp;，就返回-1。</p>\n",
    "\n",
    "<p><strong>注意：</strong> <code>n</code> 可能不符合 64 位带符号整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>最小的答案是 n = 1，其长度为 1。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 2\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>不存在可被 2 整除的正整数 n 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>k = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最小的答案是 n = 111，其长度为 3。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-integer-divisible-by-k](https://leetcode.cn/problems/smallest-integer-divisible-by-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-integer-divisible-by-k](https://leetcode.cn/problems/smallest-integer-divisible-by-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '2', '3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        if K % 2 == 0 or K % 5 == 0: \n",
    "            return -1\n",
    "        \n",
    "        r = 0\n",
    "        for N in range(1, K + 1):\n",
    "            r = (r * 10 + 1) % K\n",
    "            if r == 0: \n",
    "                return N\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        n = 1 % k\n",
    "        for i in range(1, k + 1):\n",
    "            if n == 0:\n",
    "                return i\n",
    "            n = (n * 10 + 1) % k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 2 == 0 or k % 5 == 0:\n",
    "            return -1\n",
    "        ans, resid = 1, 1   # ans 表示长度，resid 表示余数\n",
    "        while resid % k != 0:   # 当余数不为 0 时\n",
    "            resid = (resid % k) * (10 % k) + 1\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 2 == 0 or k % 5 == 0:\n",
    "            return -1\n",
    "        # 同余原理\n",
    "        ans, resid = 1, 1  # ans 表示长度，resid 表示余数\n",
    "        while resid % k != 0:  # 当余数不为 0 时\n",
    "            resid = (resid % k) * (10 % k) + 1 % k  # 模拟除法运算，计算下一次的余数\n",
    "            ans += 1  # 长度加 1\n",
    "            \n",
    "        return ans  # 返回最小整数的长度\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 2 == 0 or k % 5 == 0:\n",
    "            return -1\n",
    "        # 同余原理 \n",
    "        # (a+b) % k = a%k + b%k\n",
    "        # (ab) % k = ((a%k)(b%k))%k\n",
    "        ans, resid = 1, 1  # ans 表示长度，resid 表示余数\n",
    "        while resid % k != 0:  # 当余数不为 0 时\n",
    "            # 防止溢出以及运算量过大,使用同余原理,resid = resid*10+1,余数为resid%k + 10%k + 1%k\n",
    "            resid = (resid % k) * (10 % k) + 1  # 模拟除法运算，计算下一次的余数\n",
    "            ans += 1  # 长度加 1\n",
    "            \n",
    "        return ans  # 返回最小整数的长度\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 2 == 0 or k % 5 == 0:\n",
    "            return -1\n",
    "        else:\n",
    "            n = 1\n",
    "            ans = 1\n",
    "            while n % k != 0:\n",
    "                n = (n % k) *(10 % k) + 1\n",
    "                ans += 1\n",
    "            return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 2 == 0 or k % 5 == 0:\n",
    "            return -1\n",
    "        n = 1\n",
    "        for i in range(1, 1000000):\n",
    "            if n % k == 0:\n",
    "                return i\n",
    "            n = n * 10 + 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 2 == 0 or k % 5 == 0: \n",
    "            return -1 \n",
    "        \n",
    "        n = len(str(k))\n",
    "        tmp = int(''.join(['1'] * n))\n",
    "\n",
    "        for i in range(n,50000):\n",
    "            \n",
    "            if tmp % k == 0:\n",
    "                return i \n",
    "            tmp = tmp * 10 + 1\n",
    "\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        n=1\n",
    "        left=n%k #初始n==1\n",
    "        for i in range(1,k+1):#i为位数\n",
    "            if left==0:\n",
    "                return i\n",
    "            n=n*10+1\n",
    "            left=n%k\n",
    "            \n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        exist = [False]*k\n",
    "        res = 1 % k\n",
    "        le = 1\n",
    "        while res != 0 and not exist[res]:\n",
    "            exist[res] = True\n",
    "            res = (res * 10 + 1) % k\n",
    "            le += 1\n",
    "        if res != 0:\n",
    "            return -1\n",
    "        return le\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        n=1\n",
    "        if 1%k==0:\n",
    "            return 1\n",
    "        res=1\n",
    "        a=[0]*k\n",
    "         \n",
    "        \n",
    "        while res!=0:\n",
    "            res=((res*(10%k))%k+1)%k\n",
    "            if a[res]:\n",
    "                return -1\n",
    "            a[res]=1\n",
    "            n+=1\n",
    "        return n\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 2 == 0 or k % 5 == 0:\n",
    "            return -1\n",
    "        cnt = 1\n",
    "        ℹ = 1\n",
    "        while cnt % k != 0 and cnt < float('inf'):\n",
    "            cnt = cnt * 10 + 1\n",
    "            i += 1\n",
    "        return i if cnt < float('inf') else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k & 1 is 0 or k % 5 is 0:\n",
    "            return -1\n",
    "        if k == 1:\n",
    "            return 1\n",
    "\n",
    "        ans, r = 1, 1\n",
    "        rs = [0] * k\n",
    "        while r:\n",
    "            if rs[r] == 1:\n",
    "                return -1\n",
    "            rs[r] = 1\n",
    "            r = (r * 10 + 1) % k\n",
    "            ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        res = [0] * k\n",
    "        curr = 1\n",
    "        for cnt in range(k):\n",
    "            tmp = curr % k\n",
    "            if tmp == 0:\n",
    "                return cnt+1\n",
    "            elif res[tmp]:\n",
    "                return -1\n",
    "            else:\n",
    "                res[tmp] = 1\n",
    "                curr = 10 * tmp + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        resid = [-1] * k\n",
    "        if int(str(k)[-1]) not in [1,3,7,9]:\n",
    "            return -1\n",
    "        else:\n",
    "            s = 1\n",
    "            num = 1\n",
    "            while resid[0] == -1:\n",
    "                r = s % k\n",
    "                if r == 0:\n",
    "                    return num \n",
    "                elif r != 0 and resid[r] == -1:\n",
    "                    resid[r] = 1\n",
    "                    s = 10 * s + 1\n",
    "                    num += 1\n",
    "                elif resid[r] == 1:\n",
    "                    return -1\n",
    "                    \n",
    "                \n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        now = 0\n",
    "        vis = [0 for i in range(k)]\n",
    "        len = 0\n",
    "        while True :\n",
    "            len += 1\n",
    "            now = now * 10 + 1\n",
    "            now %= k\n",
    "            if now == 0 :\n",
    "                return len\n",
    "            if vis[now] == 1 :\n",
    "                return -1\n",
    "            vis[now] = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\t\tdef smallestRepunitDivByK(self, k: int) -> int:\n",
    "\t\t\tif k%2==0 or k%5==0:\n",
    "\t\t\t\treturn -1\n",
    "\t\t\tn, cur = 1, 1\n",
    "\t\t\ts = [0] * k\n",
    "\t\t\twhile True:\n",
    "\t\t\t\tr = cur % k\n",
    "\t\t\t\tif r == 0:\n",
    "\t\t\t\t\treturn n\n",
    "\t\t\t\tif s[r] != 0:\n",
    "\t\t\t\t\treturn -1\n",
    "\t\t\t\ts[r] = 1\n",
    "\t\t\t\tcur = cur * 10 + 1\n",
    "\t\t\t\tn += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        res, rem = 1, 1%k\n",
    "        check = [0 for _ in range(k)]\n",
    "        while rem != 0:\n",
    "            res += 1\n",
    "            check[rem] = 1\n",
    "            rem = (rem * 10 + 1) % k\n",
    "            if check[rem]:\n",
    "                return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        now = 0\n",
    "        vis = [0 for i in range(k)]\n",
    "        len = 0\n",
    "        while True :\n",
    "            len += 1\n",
    "            now = now * 10 + 1\n",
    "            now %= k\n",
    "            if now == 0 :\n",
    "                return len\n",
    "            if vis[now] == 1 :\n",
    "                return -1\n",
    "            vis[now] = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        h = [0]*100005\n",
    "        ans = 0\n",
    "        a = 0\n",
    "        while 1:\n",
    "            ans += 1\n",
    "            a = ((a*(10%k))%k+1)%k\n",
    "            if a==0:\n",
    "                return ans\n",
    "            if h[a]:\n",
    "                return -1\n",
    "            else:\n",
    "                h[a]+=1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def smallest_repunit_divK_v1(self, k: int) -> int:\n",
    "\n",
    "        def get_multiple(remainder: int) -> int:\n",
    "            remainder = 1 - remainder\n",
    "            if remainder < 0:\n",
    "                remainder = -(remainder // 10) * 10 + remainder\n",
    "\n",
    "            nonlocal k\n",
    "            for i in range(10):\n",
    "                if ((i * k) % 10) == remainder:\n",
    "                    return i\n",
    "            return -1\n",
    "\n",
    "        resi = 0\n",
    "        rst = []\n",
    "\n",
    "        while True:\n",
    "            item = get_multiple(resi)\n",
    "            if item == -1:\n",
    "                return -1\n",
    "            rst.append(item)\n",
    "            resi = (item * k + resi) // 10\n",
    "            if resi == 0:\n",
    "                break\n",
    "\n",
    "        return len(rst)\n",
    "\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        return self.smallest_repunit_divK_v1(k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        if K % 2 == 0 or K % 5 == 0: \n",
    "            return -1\n",
    "        t=1\n",
    "        mod=set()\n",
    "        n=t%K\n",
    "        while n not in mod:\n",
    "            if n==0:\n",
    "                return len(str(t))\n",
    "            else:\n",
    "                mod.add(n)\n",
    "                t=t*10+1     \n",
    "                n=t %K     \n",
    "        return -1\n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        x=1\n",
    "        n=1\n",
    "        visited=set()\n",
    "        while x%K!=0:\n",
    "            if x in visited:\n",
    "                return -1\n",
    "            visited.add(x)\n",
    "            x=10*(x%K)+1\n",
    "            n+=1\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        dividend = 1\n",
    "        remainder = 0\n",
    "        pre_remainder = [-1]\n",
    "        n = 1\n",
    "        while remainder not in pre_remainder :\n",
    "            pre_remainder.append(remainder)\n",
    "            dividend = remainder * 10 + 1\n",
    "            remainder = dividend % k\n",
    "            # print(remainder, pre_remainder, dividend)\n",
    "            if remainder == 0: return n\n",
    "            n += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "\n",
    "        denote = set()\n",
    "        remain = 0\n",
    "        \n",
    "        lens = 0\n",
    "        while True:\n",
    "            remain = remain * 10 + 1\n",
    "            lens += 1\n",
    "            if remain >= K:\n",
    "                remain = remain % K\n",
    "                if remain == 0:\n",
    "                    return lens\n",
    "                elif remain in denote:\n",
    "                    return -1\n",
    "                else:\n",
    "                    denote.add(remain)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        # if K % 2 == 0 or K % 5 == 0: return -1\n",
    "        # x, cnt = 0, 0\n",
    "        # while True:\n",
    "        #     x = x * 10 + 1\n",
    "        #     cnt += 1\n",
    "        #     x = x % K\n",
    "        #     if x == 0: return cnt\n",
    "        x, cnt, hashmap = 0, 0, set()\n",
    "        while True:\n",
    "            x = x * 10 + 1\n",
    "            cnt += 1\n",
    "            x = x % K\n",
    "            if x == 0: return cnt\n",
    "            if x in hashmap: return -1\n",
    "            hashmap.add(x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        if K==1:\n",
    "            return 1\n",
    "        q_set = set()\n",
    "        c = 1\n",
    "        q = 1\n",
    "        i = 1\n",
    "        while True:\n",
    "            i += 1\n",
    "            c = 10*q + 1\n",
    "            q = c%K\n",
    "            if c>=K:\n",
    "                if q == 0:\n",
    "                    return i\n",
    "                elif q in q_set:\n",
    "                    return -1\n",
    "                else:\n",
    "                    q_set.add(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        if K%10 in [2,4,5,6,8]:\n",
    "            return -1\n",
    "        seen = set()\n",
    "        mod = 0\n",
    "        for i in range(1,K+1):\n",
    "            mod = (mod*10+1)%K\n",
    "\n",
    "            if mod in seen:\n",
    "                return -1\n",
    "\n",
    "            if mod == 0:\n",
    "                return i\n",
    "\n",
    "            seen.add(mod)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        if K % 10 not in {1,3,7, 9}: return -1\n",
    "        remains = set()\n",
    "        n = result = 1\n",
    "        while True:\n",
    "            r = n % K\n",
    "            if not r: return result\n",
    "            if r in remains: return -1\n",
    "            remains.add(r)\n",
    "            n = n * 10 + 1\n",
    "            result += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        if K % 2 == 0:  # 节省一点时间\n",
    "            return -1\n",
    "\n",
    "        n = 1\n",
    "        r = n % K\n",
    "        s = {r}\n",
    "        while True:\n",
    "            if r == 0:\n",
    "                return len(s)\n",
    "\n",
    "            r = ((r * 10) % K + 1) % K\n",
    "            if r in s:\n",
    "                return -1\n",
    "            s.add(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK_(self, K: int) -> int:\n",
    "        dic = {2,4,5,6,8,0}\n",
    "        if K % 10 in dic: return -1\n",
    "        num, mod_set = 0, set()\n",
    "        while True:\n",
    "            num = 10 * num + 1\n",
    "            tmp = num % K\n",
    "            if tmp == 0: return len(str(num))\n",
    "            if tmp in mod_set: return -1\n",
    "            mod_set.add(tmp)\n",
    "    def smallestRepunitDivByK(self, K):\n",
    "        if K % 10 not in {1, 3, 7, 9}: return -1\n",
    "        mod, mod_set, length = 0, set(), 0\n",
    "        while True:\n",
    "            mod = (10 * mod + 1) % K\n",
    "            length += 1\n",
    "            if mod == 0: return length\n",
    "            if mod in mod_set: return -1\n",
    "            mod_set.add(mod)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# auther yeling\n",
    "from typing import List\n",
    "from bisect import *\n",
    "from collections import *\n",
    "from functools import *\n",
    "from itertools import *\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import Optional\n",
    "import string\n",
    "\n",
    "INF = 2 ** 64 - 1\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK2(self, k: int) -> int:\n",
    "        if k % 2 == 0 or k % 5 == 0:\n",
    "            return -1\n",
    "        curr = 1\n",
    "        while curr % k != 0:\n",
    "            curr = curr * 10 + 1\n",
    "        # print(curr, curr//k, len(str(curr)))\n",
    "        return len(str(curr))\n",
    "\n",
    "\n",
    "    # 68 / 70\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 2 == 0 or k % 5 == 0:\n",
    "            return -1\n",
    "        #1 11特殊处理\n",
    "        if str(k).count('1') == len(str(k)):\n",
    "            return len(str(k))\n",
    "        # 1, 3, 7, 9\n",
    "        ans = []\n",
    "        b = []\n",
    "        temp = k\n",
    "        while temp > 0:\n",
    "            b.append(temp%10)\n",
    "            temp //= 10\n",
    "        # print(b)\n",
    "\n",
    "        a = []\n",
    "        i = 0\n",
    "        left = 0\n",
    "        while True:\n",
    "            flag = False\n",
    "            for j in range(0,10):\n",
    "                curr = j * b[0] + left\n",
    "                if curr % 10 == 1:\n",
    "                    flag = True\n",
    "                    a.append(j)\n",
    "                    ans.append(1)\n",
    "                    break\n",
    "            if flag == False:\n",
    "                return -1\n",
    "            left = curr//10\n",
    "            # left = (a[-1] * b[i])\n",
    "            for j in range(i+1):\n",
    "                if j + 1 < len(b):\n",
    "                    left += a[-1 - j] * b[j+1]\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            i += 1\n",
    "            if left == 0 and i > len(b):\n",
    "                break\n",
    "            # print(left, a)\n",
    "        # print(b, a,  ans)\n",
    "\n",
    "        return len(ans)\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        if K&1==0:\n",
    "            return -1\n",
    "        mod = 0\n",
    "        \"\"\"\n",
    "        a%k = mod\n",
    "        (a*10+1)%k = a%k * 10%k + 1 = mod * (10%k) + 1\n",
    "        \"\"\"\n",
    "        s = set()\n",
    "        for i in range(1<<31):\n",
    "            mod = (mod*(10%K) + 1)%K\n",
    "            if mod == 0:\n",
    "                return i + 1\n",
    "            elif mod in s:\n",
    "                return -1\n",
    "            s.add(mod)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        # even\n",
    "        if K & 1 == 0 or K % 5 == 0:\n",
    "            return -1\n",
    "        \n",
    "        all_one = True\n",
    "        for c in str(K):\n",
    "            if c != '1':\n",
    "                all_one = False\n",
    "                break\n",
    "        if all_one:\n",
    "            return len(str(K))\n",
    "        # max avail bit is K bit\n",
    "        # so only to loop for k time\n",
    "        # we need to know the base 1111 size\n",
    "        # base_size = len(str(K)) + 1\n",
    "        # calculate begin size\n",
    "        base_size = len(str(K))\n",
    "        begin = 1\n",
    "        for i in range(base_size):\n",
    "            begin = begin * 10 + 1\n",
    "        c = base_size + 1\n",
    "        occ = set()\n",
    "        for i in range(K):\n",
    "            mod_re = begin % K\n",
    "            if mod_re == 0:\n",
    "                return c\n",
    "            if mod_re in occ:\n",
    "                return -1\n",
    "            # size ++\n",
    "            occ.add(mod_re)\n",
    "            c += 1\n",
    "            # use mod result to go on simulation\n",
    "            begin = mod_re * 10 + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 2 == 0 or k % 5 == 0:\n",
    "            return -1\n",
    "        res_set = [1,]\n",
    "        res = 1 % k\n",
    "        n = 1\n",
    "        while res != 0:\n",
    "            res = (res * 10 + 1) % k\n",
    "            n += 1\n",
    "            if res in res_set:\n",
    "                return -1\n",
    "            res_set.append(res)\n",
    "        return n \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if (k%2==0) or (k%5==0):\n",
    "            return -1\n",
    "\n",
    "        cur_len = 1\n",
    "        number = 1\n",
    "        before_append_list = []\n",
    "        while cur_len<=k:\n",
    "            cur_append = number%k\n",
    "            if cur_append==0:\n",
    "                return cur_len\n",
    "            else:\n",
    "                if cur_append in before_append_list:\n",
    "                    return -1\n",
    "                before_append_list.append(cur_append)\n",
    "            number *=10\n",
    "            number += 1\n",
    "            cur_len += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k%2==0:\n",
    "            return -1\n",
    "        if k==1:\n",
    "            return 1\n",
    "        ans=[1]\n",
    "        res=1\n",
    "        while 1:\n",
    "            b=(ans[-1]*10+1)%k\n",
    "            if b in ans:\n",
    "                return -1\n",
    "            if b==0:\n",
    "                return res+1\n",
    "            else:\n",
    "                ans.append(b)\n",
    "                res=res+1\n",
    "        return res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 2 == 0 or k % 5 == 0:\n",
    "            return -1\n",
    "        cur = []\n",
    "        n = 1\n",
    "        r = n % k\n",
    "        if r == 0:\n",
    "            return 1\n",
    "        for i in range(1, k):\n",
    "            r = (r * 10 + 1) % k\n",
    "            if r == 0:\n",
    "                return i + 1\n",
    "            if r in cur:\n",
    "                return -1\n",
    "            else:\n",
    "                cur.append(r)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        res_new = 1\n",
    "        l = []\n",
    "        total_num = 1\n",
    "        while res_new % k != 0:\n",
    "            # 更新res_new的值\n",
    "            if res_new in l:\n",
    "                return -1\n",
    "            else:\n",
    "                l.append(res_new)\n",
    "            res_new = (res_new*10 + 1) % k\n",
    "            total_num += 1\n",
    "        return total_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        length=1\n",
    "        mod_value = 1%k\n",
    "        all_mod_value = [mod_value]\n",
    "        while mod_value>0:\n",
    "            next_mod_value = (mod_value*10+1)%k\n",
    "            if(next_mod_value in all_mod_value):\n",
    "                length = -1\n",
    "                break\n",
    "            else:\n",
    "                length = length + 1\n",
    "                all_mod_value.append(next_mod_value)\n",
    "                mod_value = next_mod_value\n",
    "        return length\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 2 == 0 or k % 5 ==0:\n",
    "            return -1\n",
    "        \n",
    "        mid = []\n",
    "        reside = 1 % k\n",
    "        mid.append(reside)\n",
    "        res = 1\n",
    "        while reside != 0:\n",
    "            reside = (reside * 10 + 1) % k\n",
    "            if reside in mid:\n",
    "                return -1\n",
    "            else:\n",
    "                mid.append(reside)\n",
    "                res=res+1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        list_i=[]\n",
    "        m=1\n",
    "        remod=1%k \n",
    "        length=1\n",
    "        while(remod!=0):\n",
    "            list_i.append(remod)\n",
    "            m=m*10+1\n",
    "            remod=(remod*10+1)%k \n",
    "            length+=1\n",
    "            if remod in list_i:\n",
    "                return -1\n",
    "        return length\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef smallestRepunitDivByK(self,K):\n",
    "\t\tans,now=1,1%K\n",
    "\t\thas={now:True}\n",
    "\t\twhile now:\n",
    "\t\t\tnow=((now*10)|1)%K\n",
    "\t\t\tans+=1\n",
    "\t\t\ttry:\n",
    "\t\t\t\treturn has[now] and -1\n",
    "\t\t\texcept KeyError:\n",
    "\t\t\t\thas[now]=True\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        # https://leetcode-cn.com/problems/smallest-integer-divisible-by-k/comments/69290\n",
    "        # if K % 2 == 0 or K % 5 == 0: return -1\n",
    "        # x, cnt = 0, 0\n",
    "        # while True:\n",
    "        #     cnt += 1\n",
    "        #     x = 10 * x + 1\n",
    "        #     x = x % K\n",
    "        #     if x == 0: return cnt\n",
    "        # x, cnt, hashmap = 1, 1, {}\n",
    "        # while x % K != 0:\n",
    "        #     x = x % K\n",
    "        #     if x in hashmap: return -1\n",
    "        #     hashmap[x] = 1\n",
    "        #     x = 10 * x + 1\n",
    "        #     cnt += 1\n",
    "        # return cnt\n",
    "\n",
    "        x, cnt, hashmap = 0, 0, {}\n",
    "        while True:\n",
    "            x = 10 * x + 1\n",
    "            cnt += 1\n",
    "            x = x % K\n",
    "            if x == 0: return cnt\n",
    "            if x in hashmap: return -1\n",
    "            hashmap[x] = 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        if K%10 in [2, 4, 5, 6, 8, 0]:\n",
    "            return -1\n",
    "        n = 1\n",
    "        visited = set()\n",
    "        cnt = 1\n",
    "        while True:\n",
    "            if n < K:\n",
    "                cnt += 1\n",
    "                n = n*10 + 1\n",
    "                continue\n",
    "            remain = n%K\n",
    "            if remain == 0:\n",
    "                return cnt\n",
    "            elif remain in visited:\n",
    "                return -1\n",
    "            else:\n",
    "                visited.add(remain)\n",
    "                n = remain*10 + 1\n",
    "                cnt += 1\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        base = 1\n",
    "        cache = set()\n",
    "        ret = 0\n",
    "        cur = 0\n",
    "        while cur not in cache:\n",
    "            cache.add(cur)\n",
    "            mod = base % k\n",
    "            base = mod*10\n",
    "            cur = (cur+mod)%k\n",
    "            ret += 1\n",
    "            if cur == 0:\n",
    "                return ret\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 1\n",
    "        shown = set()\n",
    "        res = 1\n",
    "        rem = 1\n",
    "        while rem != 0:\n",
    "            if rem in shown:\n",
    "                return -1\n",
    "            shown.add(rem)\n",
    "            rem = (rem * 10 + 1) % k\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        # if K % 10 in [2, 4, 5, 6, 8]:\n",
    "        #     return - 1\n",
    "        seen = set()\n",
    "        mod = 0\n",
    "        for i in range(1, K + 1):\n",
    "            # Xi+1 = (10 * Xi + 1) \n",
    "            # MODi+1 = Xi+1 % k = (10 * Xi + 1) % k = (10 * MODi + 1) % k\n",
    "            # print(int(\"1\" * i))\n",
    "            # mod = int(\"1\" * i) % K\n",
    "            mod = (mod * 10 + 1) % K\n",
    "            if mod in seen:\n",
    "                return -1\n",
    "            if mod == 0:\n",
    "                return i\n",
    "            seen.add(mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        seen = set()\n",
    "        remainder = 1\n",
    "        step = 1\n",
    "        while True:\n",
    "            remainder = remainder%k\n",
    "            if remainder in seen:\n",
    "                return -1\n",
    "            if remainder == 0:\n",
    "                return step\n",
    "            else:\n",
    "                seen.add(remainder)\n",
    "                remainder = remainder*10 + 1\n",
    "                step += 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        # if K % 10 in [2, 4, 5, 6, 8]:\n",
    "        #     return - 1\n",
    "        seen = set()\n",
    "        mod = 0\n",
    "        for i in range(1, K+100 + 1):\n",
    "            # Xi+1 = (10 * Xi + 1) \n",
    "            # MODi+1 = Xi+1 % k = (10 * Xi + 1) % k = (10 * MODi + 1) % k\n",
    "            # print(int(\"1\" * i))\n",
    "            # mod = int(\"1\" * i) % K\n",
    "            mod = (mod * 10 + 1) % K\n",
    "            if mod in seen:\n",
    "                return -1\n",
    "            if mod == 0:\n",
    "                return i\n",
    "            seen.add(mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 10 not in (1, 3, 7, 9):\n",
    "            return -1\n",
    "        nums = [0] * 10\n",
    "        for i in range(10):\n",
    "            num = i * k\n",
    "            nums[num % 10] = num\n",
    "        ans = 0\n",
    "        seen = set()\n",
    "        while k:\n",
    "            if k in seen:\n",
    "                return -1\n",
    "            seen.add(k)\n",
    "            k = (k + nums[(1 - k % 10) % 10]) // 10\n",
    "            ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def smallestRepunitDivByK(self, K: int) -> int:\n",
    "        # if K % 10 in [2, 4, 5, 6, 8]:\n",
    "        #     return - 1\n",
    "        seen = set()\n",
    "        mod = 0\n",
    "        for i in range(1, K + 1):\n",
    "            # Xi+1 = (10 * Xi + 1) \n",
    "            # MODi+1 = Xi+1 % k = (10 * Xi + 1) % k = (10 * MODi + 1) % k\n",
    "            # print(int(\"1\" * i))\n",
    "            # mod = int(\"1\" * i) % K\n",
    "            mod = (mod * 10 + 1) % K\n",
    "            if mod in seen:\n",
    "                return -1\n",
    "            if mod == 0:\n",
    "                return i\n",
    "            seen.add(mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k & 0x01 == 0:\n",
    "            return -1\n",
    "        n = 0\n",
    "        ret = 0\n",
    "        while n < k:\n",
    "            n = n * 10 + 1\n",
    "            ret += 1\n",
    "        \n",
    "        visited = set()\n",
    "        while n % k != 0:\n",
    "            r = n % k\n",
    "            if r in visited:\n",
    "                return -1\n",
    "            visited.add(r)\n",
    "            n = r * 10 + 1\n",
    "            ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        ans, mod, vis = 1, 1%k, set()\n",
    "        while mod:\n",
    "            mod = (mod*10+1)%k\n",
    "            if mod in vis: return -1\n",
    "            vis.add(mod)\n",
    "            ans+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        seen = [] # 见过的余数\n",
    "        leng = len(str(k))\n",
    "        num = ''\n",
    "        for i in range(leng):\n",
    "            num += '1'\n",
    "        if int(num)==k:\n",
    "            return leng\n",
    "        elif int(num)>k:\n",
    "            a = 1\n",
    "        elif int(num)<k:\n",
    "            leng += 1\n",
    "            num += '1'\n",
    "        num = int(num)%k\n",
    "        \n",
    "        print(num)\n",
    "        while num!=0 and num not in seen:\n",
    "            seen.append(num)\n",
    "            num = (10*num+1)%k \n",
    "            print(num)\n",
    "            leng+=1\n",
    "            # seen.append(num)\n",
    "        print(seen)\n",
    "        if num>0:\n",
    "            return -1\n",
    "        else:\n",
    "            return leng\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if not str(k)[-1] in '1379': return -1\n",
    "        ret=[]\n",
    "        mod=0\n",
    "        s=set() \n",
    "        #\n",
    "        while True: \n",
    "            #print(s)\n",
    "            \n",
    "            mod=(mod*10+1)%k\n",
    "            if mod in s: return -1 \n",
    "            #print(mod)\n",
    "            ret.append(1) \n",
    "            if mod==0: return len(ret) \n",
    "            s.add(mod) \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        vis, s, i = set(), 0, 0\n",
    "        while True:\n",
    "            s = (s*10+1)%k\n",
    "            i += 1\n",
    "            if s==0:\n",
    "                return i\n",
    "            if s in vis:\n",
    "                return -1\n",
    "            vis.add(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        vis, s, i = set(), 0, 0\n",
    "        while s not in vis:\n",
    "            vis.add(s)\n",
    "            s = (s*10+1)%k\n",
    "            i += 1\n",
    "            if s==0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        r=1\n",
    "        le=1\n",
    "        seen=set()\n",
    "        while True:\n",
    "            if r%k==0:\n",
    "                return le\n",
    "            elif r in seen:\n",
    "                return -1\n",
    "            else:\n",
    "                seen.add(r)\n",
    "                r=(r*10+1)%k\n",
    "                le+=1\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "\n",
    "        if k==1:\n",
    "            return 1\n",
    "        if k%2==0:\n",
    "            return -1\n",
    "        if k%5==0:\n",
    "            return -1\n",
    "\n",
    "        ss = set()\n",
    "        r = 1\n",
    "        t = 1\n",
    "        while t!=0:\n",
    "            if t in ss:\n",
    "                return -1\n",
    "            ss.add(t)\n",
    "            t=(10*t+1)%k\n",
    "            r+=1\n",
    "        return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self,K):\n",
    "            ans,now=1,1%K\n",
    "            has={now:True}\n",
    "            while now:\n",
    "                    now=((now*10)|1)%K\n",
    "                    ans+=1\n",
    "                    try:\n",
    "                        return has[now] and -1\n",
    "                    except KeyError:\n",
    "                        has[now]=True\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 1\n",
    "        \n",
    "        left = 1\n",
    "        nums = 1\n",
    "        hashmap = collections.defaultdict()\n",
    "\n",
    "        while left > 0:\n",
    "            left = left * 10 + 1\n",
    "            left = left % k\n",
    "            nums += 1\n",
    "            if left == 0:\n",
    "                return nums\n",
    "            if left not in hashmap:\n",
    "                hashmap[left] = 1\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k==1:\n",
    "            return 1\n",
    "        mod=1\n",
    "        ans=1\n",
    "        hsh={1:1}\n",
    "        while True:\n",
    "            mod = ((10 * mod) % k + 1) % k\n",
    "            ans+=1\n",
    "            if mod in hsh:\n",
    "                return -1\n",
    "            hsh[mod]=1\n",
    "            if mod ==0:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        s = set()\n",
    "        pre = 0\n",
    "        l = 1\n",
    "\n",
    "        while 0 not in s:\n",
    "            pre = (pre*10+1) % k\n",
    "            if pre in s:\n",
    "                return -1\n",
    "            s.add(pre)\n",
    "            l += 1\n",
    "\n",
    "        return l-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 2 ==0 or k % 5 ==0:\n",
    "            return -1\n",
    "        resid = set([])\n",
    "        n = 1\n",
    "        ans = 1\n",
    "        while True:\n",
    "            res = n % k\n",
    "            if res in resid:\n",
    "                return -1\n",
    "            elif res == 0 :\n",
    "                return ans\n",
    "            else:\n",
    "                resid.add(res)\n",
    "                n = n*10 +1\n",
    "                ans +=1\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        s = set()       # 集合记录出现的余数\n",
    "        remain = 1 % k  # 初始n=1模k的结果\n",
    "        length = 1      # 初始n=1， 长度为1\n",
    "        while remain != 0: \n",
    "            s.add(remain)   # 出现的余数加入集合\n",
    "            remain = (remain * 10 + 1) % k  # 更新余数\n",
    "            length += 1                     # 更新长度\n",
    "            if remain in s:\n",
    "                return -1                 # 重复余数 无解\n",
    "        return length\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        redis = 1 % k\n",
    "        vis = {1 %  k}\n",
    "        n = 1\n",
    "        while redis != 0:\n",
    "            redis = (10 * redis + 1) % k\n",
    "            if redis in vis:\n",
    "                return -1\n",
    "            vis.add(redis)\n",
    "            n += 1\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        redis = 1 % k\n",
    "\n",
    "        vis = set()\n",
    "        n = 1\n",
    "        while redis != 0:\n",
    "            redis = (redis * 10 + 1) % k\n",
    "            if redis in vis:\n",
    "                return -1\n",
    "            n += 1\n",
    "            vis.add(redis)\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestRepunitDivByK(self, k: int) -> int:\n",
    "        if k % 2 == 0 or k % 5 == 0:\n",
    "            return -1\n",
    "        cur = set()\n",
    "        r = 1 % k\n",
    "        i = 1\n",
    "        while r != 0 and r not in cur:\n",
    "            if r in cur:\n",
    "                return -1\n",
    "            cur.add(r)\n",
    "            r = (r * 10 + 1) % k\n",
    "            i += 1\n",
    "        return i\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
